package day_2022_4_to_7.day48;

import java.util.Scanner;

/**
 * 查找两个字符串a,b中的最长公共子串
 * @author haomin
 * @date 2022/05/16 09:02
 **/
public class Day19_2_LongestComSubByAB {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String str1 = in.next();
        String str2 = in.next();

        String maxS = str1.length() > str2.length() ? str1:str2;
        String minS = str1.length() > str2.length() ? str2:str1;

        // 方法一
        fun1(maxS,minS);
        // 方法二
        fun2(maxS,minS);
    }

    // 方法一
    private static void fun1(String maxS, String minS) {
        String result = "";
        int length = 0;
        for (int i = 0; i < minS.length(); i++) {
            for (int j = i+1; j <= minS.length(); j++) {
                if(maxS.contains(minS.substring(i,j)) && j-i > length){
                    length = j-i;
                    result = minS.substring(i,j);
                }
            }
        }
        System.out.println(result);
    }

    // 方法二
    private static void fun2(String maxS, String minS) {
        int[][] dp = new int[minS.length()+1][maxS.length()+1];
        int maxLength = 0;
        int startIndex = 0;
        for (int i = 0; i < minS.length(); i++) {
            for (int j = 0; j < maxS.length(); j++) {
                if(minS.charAt(i) == maxS.charAt(j)){
                    dp[i+1][j+1] = dp[i][j] + 1;
                    if(dp[i+1][j+1] > maxLength){
                        maxLength = dp[i+1][j+1];
                        startIndex = i-maxLength+1;
                    }
                }
            }
        }
        System.out.println(minS.substring(startIndex,startIndex+maxLength));
    }
}